ACL Beginner Contest

https://gyazo.com/cf293b51cdb0f3e61921e381956d2872

Wow, 9 more points and light blue! Too close to call!

https://gyazo.com/9dabf4b98969d40e2b5509564cfe5ff0

https://gyazo.com/f4f4a47bc47a888934ec7935d5699512

careless mistake

Ugly conditional expression because it was fixed in a big hurry.

code:python

A, B, C, D = map(int, input().split())

# if A <= D <= B or A <= C <= B: # NG

if A <= D <= B or A <= C <= B or C <= A <= D:

print("Yes")

else:

print("No")

If you think about it calmly, it looks like this

code:python

A, B, C, D = map(int, input().split())

if D < A or B < C:

print("No")

else:

print("Yes")

https://gyazo.com/d392de5b2ccc1dc816648fb819b6adbf

Just count how many clumps of connected cities there are (let's say X) and draw a path from one of them to the remaining X-1 clumps.

code:python

def solve(N, M, edges):

init_unionfind(N)

for e in edges:

s = set(find_root(x) for x in range(N))

return len(s) - 1

https://gyazo.com/13fcd06d7d09419948c239f846aedff7

I don't know how to attribute this to ACL, so I'll write it plainly first.

Submitted, but WA/TLE mixed.

Even if I could get a WA, it would be a TLE, and I don't have a clue how to resolve this, so I put it on hold and did an E.

Dynamic programming where the trailing value is the definition range and the longest length is the value range

When the i-th value is A, the max of the K values before and after A is the "longest sequence of values that can be connected to the i-th value," so update by adding 1 to it

Samples go through below.

code:python

def solve(N, K, AS):

for i in range(1, N):

start = max(0, A - K)

return max(count)

Point update range max, so segment trees can be used.

Segment tree version AC

code:python

def solve(N, K, AS):

MAX_CAPACITY = 300_000

set_width(MAX_CAPACITY + 10)

for i in range(1, N):

start = max(0, A - K)

end = min(A + K + 1, MAX_CAPACITY + 1)

best = range_reduce(count, start, end, max, -INF)

point_set(count, A, best + 1, max)

return range_reduce(count, 0, MAX_CAPACITY + 1, max, -INF)

Hammer Point

https://gyazo.com/2bd499438884da4227a67110c503b545

I thought it might be a twin segment tree because of the range update.

I reworked my own library in a big hurry because the binary operation does not take size as an argument.

another solution

E had (length, sum). I think having (10^n, sum) is computationally better without mod pow.

code:python

def main():

# parse input

N, Q = map(int, input().split())

set_width(N + 1)

value_unity = 0

action_unity = None

cache11 = {}

i = 1

p = 1

step = 10

while i <= N:

p = (p * step + p) % MOD

step = (step * step) % MOD

i *= 2

cache10 = {0: 1}

i = 1

p = 10

while i <= N:

p = (p * 10) % MOD

i += 1

def action_force(action, value, size):

if action == action_unity:

return value

# return int(str(action) * size)

def action_composite(new_action, old_action):

if new_action == action_unity:

return old_action

return new_action

def value_binop(a, b, size):

# return (a * (10 ** size) + b) % MOD

full_up(value_table, value_binop)

for _q in range(Q):

l, r, d = map(int, input().split())

lazy_range_update(

action_table, value_table, l - 1, r, d,

action_composite, action_force, action_unity, value_binop)

ret = lazy_range_reduce(

action_table, value_table, 0, N, action_composite, action_force, action_unity,

value_binop, value_unity)

print(ret)

F

---